#![allow(dead_code)]
use std::{collections::VecDeque, vec};

#[derive(Debug)]
pub struct MinStack {
    stack: Vec<i32>,
    minstack: Vec<i32>,
}

impl MinStack {
    pub fn new() -> Self {
        Self {
            stack: vec![],
            minstack: vec![],
        }
    }

    pub fn push(&mut self, data: i32) -> &mut Self {
        self.stack.push(data);

        if self.minstack.is_empty() || *self.minstack.last().unwrap() > data {
            self.minstack.push(data);
        }

        self
    }

    pub fn pop(&mut self) -> i32 {
        let num = self.stack.pop().unwrap();

        if num == *self.minstack.last().unwrap() {
            self.minstack.pop();
        }

        num
    }

    pub fn get_min(&self) -> i32 {
        *self.minstack.last().unwrap()
    }

    pub fn top(&self) -> i32 {
        *self.stack.last().unwrap()
    }
}

pub struct SlideWin {
    pub nums: Vec<i32>,
    pub k: usize,
    pub deque: VecDeque<i32>,
    pub max_vec: Vec<i32>,
}

impl SlideWin {
    pub fn new(nums: Vec<i32>, k: usize) -> Self {
        Self {
            nums,
            k,
            deque: VecDeque::new(),
            max_vec: vec![],
        }
    }

    pub fn frist_k(&mut self) -> &mut VecDeque<i32> {
        for i in 0..self.k {
            self.decreasing_push(self.nums[i]);
        }

        &mut self.deque
    }

    pub fn decreasing_push(&mut self, num: i32) -> &VecDeque<i32> {
        while !self.deque.is_empty() {
            if num >= *self.deque.back().unwrap() {
                self.deque.pop_back();
            } else {
                break;
            }
        }
        self.deque.push_back(num);
        &self.deque
    }

    pub fn max_value(&mut self) -> &Vec<i32> {
        if self.nums.len() == 0 || self.k == 1 {
            return &self.max_vec;
        }

        for i in self.k - 1..self.nums.len() {
            if i == self.k - 1 {
                self.frist_k();
                self.max_vec.push(*self.deque.front().unwrap());
            } else if i > self.k - 1 {
                self.decreasing_push(self.nums[i]);

                if *self.deque.front().unwrap() == self.nums[i - self.k] {
                    self.deque.pop_front();
                }
                self.max_vec.push(*self.deque.front().unwrap());
            }
        }

        &self.max_vec
    }
}

pub struct Solution;
impl Solution {
    pub fn is_match(s: &String) -> bool {
        if s.len() == 0 {
            return true;
        }
        let chs: Vec<char> = s.chars().collect();

        let mut v: Vec<char> = Vec::new();
        for ch in chs {
            if ch == '(' {
                v.push(')');
            } else if ch == '[' {
                v.push(']');
            } else if ch == '{' {
                v.push('}');
            } else if v.is_empty() || v.pop().unwrap() != ch {
                return false;
            }
        }

        v.is_empty()
    }
}

pub fn test_stack() {
    println!("\n========== 最小栈 ===========");
    let mut stack = MinStack::new();
    stack.push(-2).push(0).push(-3);
    println!("stack：{:?}", stack);
    println!("stack.get_min：{:?}", stack.get_min());
    println!("stack：{:?}", stack);
    println!("stack.pop：{:?}", stack.pop());
    println!("stack：{:?}", stack);
    println!("stack.top：{:?}", stack.top());
    println!("stack：{:?}", stack);
    println!("stack.get_min：{:?}", stack.get_min());
    println!("stack：{:?}", stack);

    println!("\n========== 有效的括号匹配 ===========");
    let s = "()[]{}".to_string();
    println!("{} 括号配置：{:?}", s, Solution::is_match(&s));
    let s = "{[]}".to_string();
    println!("{} 括号配置：{:?}", s, Solution::is_match(&s));
    let s = "([)]".to_string();
    println!("{} 括号配置：{:?}", s, Solution::is_match(&s));

    println!("\n========== 滑动窗口k的最大值 ===========");
    let nums: Vec<i32> = vec![];
    let k: usize = 2;
    let mut slide_win = SlideWin::new(nums, k);
    println!("nums: {:?}, k = {}", slide_win.nums, slide_win.k);
    println!("滑动窗口最大值: {:?}\n", slide_win.max_value());

    let nums: Vec<i32> = vec![1, 2, 3, 4];
    let k: usize = 1;
    let mut slide_win = SlideWin::new(nums, k);
    println!("nums: {:?}, k = {}", slide_win.nums, slide_win.k);
    println!("滑动窗口最大值: {:?}\n", slide_win.max_value());

    let nums: Vec<i32> = vec![1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3];
    let k: usize = 8;
    let mut slide_win = SlideWin::new(nums, k);
    println!("nums: {:?}\nk = {}", slide_win.nums, slide_win.k);
    println!("对前{}个元素构建初始递减队列: {:?}", k, slide_win.frist_k());
    println!("k = {}的最大值列表: {:?}\n", k, slide_win.max_value());

    let nums: Vec<i32> = vec![1, 3, -1, -3, 5, 3, 6, 7];
    let k: usize = 3;
    let mut slide_win = SlideWin::new(nums, k);
    println!("nums: {:?}\nk = {}", slide_win.nums, slide_win.k);
    println!("对前{}个元素构建初始递减队列: {:?}", k, slide_win.frist_k());
    println!("k = {}的最大值列表: {:?}\n", k, slide_win.max_value());
}
